/**
 * @Author ZhangCuirong
 * @Date 2025/9/5 8:46
 * @description:
 */
public class Solution152 {
    public int maxProduct(int[] nums) {
        int n = nums.length;

        // 定义：以 nums[i] 结尾的子数组，乘积最小为 dp1[i]
        int[] dp1 = new int[n];

        // 定义：以 nums[i] 结尾的子数组，乘积最大为 dp2[i]
        int[] dp2 = new int[n];

        // base case
        dp1[0] = nums[0];
        dp2[0] = nums[0];
        int max = Integer.MIN_VALUE;

        for (int i = 1; i < nums.length; i++) {
            dp1[i] = max(nums[i] * dp1[i - 1], nums[i] * dp2[i - 1], nums[i]);
            dp2[i] = min(nums[i] * dp1[i - 1], nums[i] * dp2[i - 1], nums[i]);
            max = Math.max(max, dp1[i]);
        }
        return max;
    }

    int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
    public static void main(String[] args) {
        Solution152 solution = new Solution152();
        System.out.println(solution.maxProduct(new int[]{2, 3, -2, 4}));
        System.out.println(solution.maxProduct(new int[]{-2, 0, -1}));
        System.out.println(solution.maxProduct(new int[]{-2, 3, -4}));
    }

}
